package com.sicheng.蓝桥.国赛准备.第十三届JavaB;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/18 9:15
 */
public class B数数 {
    /**
     * 【问题描述】
     * 任何一个大于 1 的正整数都能被分解为若干个质数相乘，比如 28 = 2×2×7
     * 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数
     * 可以被分解为 12 个质数相乘？
     */
    public static void main(String[] args) {
        int cnt = 0;
        for (int i = 2333333; i <= 23333333; i++) {
            int x = i;
            double res = 1;
            for (int j = 2; j * j <= x; j++) {
                if (x % j == 0) {
                    res = res / j * (j - 1);
                    while (x % j == 0) {
                        x /= j;
                    }
                }
            }
            if (x > 1)
                res = res / x * (x - 1);
            if ((int) Math.ceil(res) == 12)
                cnt++;
        }
        System.out.println(cnt);
    }
}
